\section{Growing Context-Sensitive Languages}

In this section we want to recapitulate the growing context-sensitive string languages. We will use this notions in combination with matrix grammars, to introduce a new class of pictures in Section~\ref{section:growing_context-sensitive_matrix_grammars}: the growing context-sensitive matrix languages. The following definition is from \cite{buntrock1998growing}:

\begin{definition}
	A string grammar $G = (N, T, S, P)$ is a \emph{growing context-sensitive grammar} (GCSG) where $N$ is a finite set of non-terminals, $T$ is a finite set of terminals, $S$ is the start symbol and $P$ is a set of production rules, where 
	\begin{compactitem}
		\item S does not appear on the right side of a rule and
		\item for any rule $(l \rightarrow r) \in P$, $l \neq S$ $|l| < |r|$. 
	\end{compactitem}
\end{definition}

The language generated by $G$ is denoted as $L(G)$ and is called growing context-sensitive language. The class of languages generated by GCSG is denoted as $\familyOf{GCSL}$. The grammars of those languages were introduced in \cite{book1973structure} as restriction of context-sensitive grammars, where any rule either contains only non-terminals and is length-increasing or generates only one terminal symbol. We will reflect, that this definition of grammars generates the same class of languages. 

\begin{proposition}
	Let $L$ be a growing context-sensitive language with $\epsilon \not\in L$. Then there exists a grammar $G = (N, T, S, P)$ with $L(G) = L$, which satisfies the following conditions:
	
	\begin{compactitem}
		\item $P \subseteq (N^+ \times N^+) \cup (N \times T)$ and
		\item for all $(l \rightarrow r) \in P$, $r \in N^+$: $|l| < |r|$. 
	\end{compactitem}
\end{proposition}

This has been shown by \cite{buntrock1996wachsende}. The set of rules only consists of special terminal rules and length-increasing rules containing only non-terminals. In the following we will refer to such a grammar as a \emph{growing context-sensitive grammar with special terminal rules}. 

Let $p, q \in (N \cup T)^+$ and $p = w_1lw_2$. We derive $q$ from $p$ if there exists a rule $(l \rightarrow r) \in P$ and $q = w_1rw_2$. We then write $p \underset{G}{\Rightarrow} q$. As usual, $\overset{*}{\Rightarrow}$ is the reflexive transitive closure of $\Rightarrow$. 

The class of context-free languages is a proper subset of $\familyOf{GCSL}$, which itself is a proper subset of the context-sensitive languages. This has been shown by \cite{buntrock1996wachsende}.  

To characterize the power of growing context-sensitive languages, we continue with an example from \cite{buntrock1996wachsende}, which is not context-free:

\begin{example}
\label{example:growing_context-sensitive}
	Let 	$G = (N, T, S, P)$ be a grammar, where
	
	\begin{compactitem}
		\item $N = \{S, A, E, M, L\}$, 
		\item $T = \{a\}$ and
		\item $
			P = \left\lbrace 
			\begin{matrix}
				S \rightarrow a,  & A \rightarrow AL,   & LE \rightarrow MME, \\
				S \rightarrow aa, & A \rightarrow aa,   & E \rightarrow aa, \\
				S \rightarrow AE, & LM \rightarrow MML, & M \rightarrow aa
			\end{matrix}\right\rbrace$.
	\end{compactitem}
\end{example}

As an example word, we can derive $a^8$ from S as follows: $S \Rightarrow AE \Rightarrow ALE \Rightarrow AMME \Rightarrow aaMME \Rightarrow aaaaME \Rightarrow aaaaaaE \Rightarrow aaaaaaaa$. 

It is obvious that this grammar is growing context-free, because any rule ${(l \rightarrow r) \in P}$ the right side is length-increasing, if $l \neq S$. The language generated by the grammar $G$ is $L(G) = \{a^{2^n} \mid n \geq 0\}$. In \cite{buntrock1996wachsende} it is shown that this language is not context-free. Which induces that the class of context-free languages is properly included in the class of growing context-sensitive languages. 

\begin{theorem}
	$\familyOf{GCSL}$ is an abstract family of languages. 
\end{theorem}

This theorem has been shown by \cite{buntrock1996wachsende}. Before we introduce our new model, we continue to describe how two-dimensional languages are generated by matrix grammars. 